package leetcode.每日一题;

import leetcode.剑指offer.pojo.TreeNode;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/25 21:57
 * @description：https://leetcode-cn.com/problems/even-odd-tree/
 */
public class 奇偶树 {
    @Test
    public void test() {
        Solution solution = new Solution();
        TreeNode root = new TreeNode(1,
                new TreeNode(10, new TreeNode(3, new TreeNode(12), new TreeNode(8)), null),
                new TreeNode(4, new TreeNode(7, new TreeNode(6), null), new TreeNode(9, null, new TreeNode(2))));
        System.out.println(solution.isEvenOddTree(root));
    }


    class Solution {
        public boolean isEvenOddTree(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            if (root == null) return true;
            queue.offer(root);
            int index = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                int pre = index % 2 == 0 ? -1 : Integer.MAX_VALUE;
                for (int i = 0; i < size; i++) {
                    TreeNode cur = queue.poll();
                    if (index % 2 == 0) {
                        if (cur.val <= pre || cur.val % 2 == 0) return false;
                    } else {
                        if (cur.val >= pre || cur.val % 2 == 1) return false;
                    }
                    pre = cur.val;
                    if (cur.left != null) {
                        queue.offer(cur.left);
                    }
                    if (cur.right != null) {
                        queue.offer(cur.right);
                    }
                }
                index++;
            }
            return true;
        }
    }
}
